{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Rotated Digits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rotatedDigits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #旋转数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。</p>\n",
    "\n",
    "<p>如果一个数的每位数字被旋转以后仍然还是一个数字，&nbsp;则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。</p>\n",
    "\n",
    "<p>现在我们有一个正整数&nbsp;<code>N</code>, 计算从&nbsp;<code>1</code> 到&nbsp;<code>N</code> 中有多少个数&nbsp;X 是好数？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> 10\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong> \n",
    "在[1, 10]中有四个好数： 2, 5, 6, 9。\n",
    "注意 1 和 10 不是好数, 因为他们在旋转之后不变。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>N&nbsp;的取值范围是&nbsp;<code>[1, 10000]</code>。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rotated-digits](https://leetcode.cn/problems/rotated-digits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rotated-digits](https://leetcode.cn/problems/rotated-digits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10', '1', '2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "将每个数单独看，一个数里头含有，2 5 6 9一定是 含有 1 8 0的可能是\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        dic = {\"0\":\"0\",\"1\":\"1\",\"2\":\"5\",\"5\":\"2\",\"6\":\"9\",\"8\":\"8\",\"9\":\"6\"}\n",
    "        s = [\"3\",\"4\",\"7\"]\n",
    "        def change(item: int):\n",
    "            item = str(item)\n",
    "            temp = \"\"\n",
    "            for i in range(len(item)):\n",
    "                if item[i] in s:\n",
    "                    return False\n",
    "                temp += dic[item[i]]\n",
    "            return int(item) != int(temp)\n",
    "        count = 0\n",
    "        for i in range(1,n+1):\n",
    "            if change(i) == True:\n",
    "                # print(i)\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(1, n+1):\n",
    "            now_number = i\n",
    "            good_number = 0\n",
    "            while now_number > 0:\n",
    "                j = now_number % 10\n",
    "                now_number = int(now_number / 10)\n",
    "                if (j == 3) or (j == 4) or (j == 7):\n",
    "                    good_number = 0\n",
    "                    break \n",
    "                elif (j == 0) or (j == 1) or (j == 8):\n",
    "                    continue\n",
    "                else:\n",
    "                    good_number = 1\n",
    "            res = res + good_number\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        diffs = (0,0,1,-1,-1,1,1,-1,0,1)\n",
    "        ##is_num 前面有没有填数字\n",
    "        ##is_limit 前面是不是n对应位置上的数，如果是，最大为si，如果不是最大填9\n",
    "        @cache\n",
    "        def f(i:int,has_diff:bool,is_limit:bool)->int:\n",
    "            if i==len(s):\n",
    "                return has_diff\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(0,up+1):\n",
    "                if diffs[d] != -1:##不是347\n",
    "                    res += f(i+1,has_diff or diffs[d],is_limit and up==d)\n",
    "            return res\n",
    "        return f(0,False,True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "# check_index = [0,1,2, 3, 4,5,6, 7,8,9]\n",
    "        check = [0,0,1,-1,-1,1,1,-1,0,1]\n",
    "        ans = 0 # 计数\n",
    "        for i in range(1,n+1):\n",
    "            nums = [int(digit) for digit in str(i)]\n",
    "            vaild = True\n",
    "            diff = False\n",
    "            for num in nums:\n",
    "                if check[num] == -1:\n",
    "                    vaild = False\n",
    "                elif check[num] == 1:\n",
    "                    diff = True\n",
    "            if vaild and diff:\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        check = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1]\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            num = [int(digit) for digit in str(i)]\n",
    "            valid, diff = True, False\n",
    "            for digit in num:\n",
    "                if check[digit] == -1:\n",
    "                    valid = False\n",
    "                elif check[digit] == 1:\n",
    "                    diff = True\n",
    "            if valid and diff:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        ans=0\n",
    "        for i in range(2,n+1):\n",
    "            if'3'in str(i)or'4'in str(i)or'7'in str(i):continue\n",
    "            elif'2'in str(i)or'5'in str(i)or'6'in str(i)or'9'in str(i):ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(1,n+1):\n",
    "            num = i\n",
    "            nums = {}\n",
    "            while num>0:\n",
    "                yushu = num%10\n",
    "                num = num//10\n",
    "                nums[yushu] = True\n",
    "            if (2 in nums.keys()) or (5 in nums.keys()) or (6 in nums.keys()) or (9 in nums.keys()):\n",
    "                if (3 not in nums.keys()) and (4 not in nums.keys()) and (7 not in nums.keys()):\n",
    "                    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        # 解法1:\n",
    "        # check = [0,0,1,-1,-1,1,1,-1,0,1]    # 设置数字对应合法性\n",
    "        # ans = 0 # 计数\n",
    "        # for i in range(1,n+1):\n",
    "        #     nums = [int(digit) for digit in str(i)]\n",
    "        #     vaild = True    # 判断是否合法，包含3、4、7为不合法\n",
    "        #     diff = False    # 判断与原数是否相同，至少包含一个2、5、6、9为不相同\n",
    "        #     # 判断1~n中每个数\n",
    "        #     for num in nums:\n",
    "        #         if check[num] == -1:\n",
    "        #             vaild = False\n",
    "        #         elif check[num] == 1:\n",
    "        #             diff = True\n",
    "        #     if vaild and diff:\n",
    "        #         ans += 1\n",
    "        # return ans\n",
    "\n",
    "        # 解法2：\n",
    "        # check = [0,0,1,-1,-1,1,1,-1,0,1] + (n-9)*[0]\n",
    "        # for i in range(n+1):\n",
    "        #     if check[i // 10] == -1 or check[i % 10] == -1:\n",
    "        #         check[i] = -1\n",
    "        #     elif check[i // 10] == 1 or check[i % 10] == 1:\n",
    "        #         check[i] = 1\n",
    "        # return check[:n+1].count(1) \n",
    "\n",
    "        # 解法3：\n",
    "        ans = 0\n",
    "        for i in range(n+1):\n",
    "            s = str(i)\n",
    "            if '3' in s or '4' in s or '7' in s:\n",
    "                continue\n",
    "            if '2' in s or '5' in s or '6' in s or '9' in s:\n",
    "                ans += 1\n",
    "        return ans \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        m = [1, 1, 0, 2, 2, 0, 0, 2, 1, 0]\n",
    "        tot = 0\n",
    "        for i in range(1, n + 1):\n",
    "            x = str(i)\n",
    "            check = True\n",
    "            tmp = 1\n",
    "            for s in x:\n",
    "                if s in \"347\":\n",
    "                    check = False\n",
    "                    break\n",
    "\n",
    "                else:\n",
    "                    tmp *= m[int(s)]\n",
    "            # print(x, tmp, check)\n",
    "            if not tmp and check:\n",
    "                tot += 1\n",
    "            \n",
    "        return tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1,n+1):\n",
    "            s = str(i)\n",
    "            nums = []\n",
    "            for j in range(len(s)):\n",
    "                nums.append(s[j])\n",
    "            \n",
    "            if ('3' in s) or ('4' in s) or ('7' in s):\n",
    "                continue\n",
    "            for j in range(len(s)):\n",
    "\n",
    "                if s[j] == '2':\n",
    "                    nums[j] = '5'\n",
    "                elif s[j] == '5':\n",
    "                    nums[j] = '2'\n",
    "                elif s[j] == '6':\n",
    "                    nums[j] = '9'\n",
    "                elif s[j] == '9':\n",
    "                    nums[j] = '6'\n",
    "\n",
    "            num = 0\n",
    "            for j in range(len(nums)):\n",
    "                num = num * 10 + int(nums[j])\n",
    "            if num!=i:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(idx, bound, diff):\n",
    "            if idx == n: return int(diff)\n",
    "            ret = 0\n",
    "            up = 9 if not bound else int(s[idx])\n",
    "            for i in range(up+1):\n",
    "                if i in [0, 1, 8]:\n",
    "                    ret += dfs(idx+1, i == up and bound, diff)\n",
    "                elif i in [2, 5, 6, 9]:\n",
    "                    ret += dfs(idx+1, i == up and bound, True)\n",
    "            return ret\n",
    "        s = str(n)\n",
    "        n = len(s)\n",
    "        return dfs(0, True, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        ans=0\n",
    "        for i in range(1,n+1):\n",
    "            if'3'in str(i)or'4'in str(i)or'7'in str(i):continue\n",
    "            elif'2'in str(i)or'5'in str(i)or'6'in str(i)or'9'in str(i):ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        set1=set('018')\n",
    "        set2=set('2569')\n",
    "        set3=set('347')\n",
    "        def helper(x):\n",
    "            flag=False\n",
    "            for c in str(x):\n",
    "                if c in set3:\n",
    "                    return False\n",
    "                if c in set2:\n",
    "                    flag=True\n",
    "            return flag\n",
    "        \n",
    "        count=0\n",
    "        for i in range(1,n+1):\n",
    "            if helper(i):\n",
    "                count+=1\n",
    "        return count\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        d = dict(zip(\"0125689\", \"0152986\"))\n",
    "        def check(x):\n",
    "            s1, s2 = str(x), \"\"\n",
    "            for c in s1:\n",
    "                if c in \"347\": return False\n",
    "                s2 += d[c]\n",
    "            return s1 != s2\n",
    "        return sum(check(x) for x in range(1, n + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "class Solution:\r\n",
    "    def rotatedDigits(self, n: int) -> int:\r\n",
    "        flags=[0,0,1,-1,-1,1,1,-1,0,1]\r\n",
    "        ret=0\r\n",
    "        for i in range(1,n+1):\r\n",
    "            diff=False\r\n",
    "            valid=True\r\n",
    "            # N=i\r\n",
    "            while i>0:\r\n",
    "                d=i%10\r\n",
    "                i//=10\r\n",
    "                if flags[d]==-1:\r\n",
    "                    valid=False\r\n",
    "                    break\r\n",
    "                if flags[d]==1:\r\n",
    "                    diff=True\r\n",
    "            if diff and valid:\r\n",
    "                ret+=1\r\n",
    "                # print(N)\r\n",
    "        return ret\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        s = {str(number) for number in [ 2, 5, 6, 9]}\n",
    "        s2 = {str(number) for number in [ 2, 5, 6, 9, 1, 0, 8]}\n",
    "        print(s)\n",
    "        res = 0\n",
    "        for i in range(1,  n+1):\n",
    "            if any([c in s for c in str(i)]) and all([c in s2 for c in str(i)]):\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def change(num):\n",
    "        nums = []\n",
    "        while(num>0):\n",
    "            bit = num % 10\n",
    "            if bit == 2:bit = 5\n",
    "            elif bit == 5:bit = 2\n",
    "            elif bit == 6:bit = 9\n",
    "            elif bit == 9:bit = 6\n",
    "            elif bit == 1:bit = 1\n",
    "            elif bit == 0:bit = 0\n",
    "            elif bit == 8:bit = 8\n",
    "            else:return 0\n",
    "            nums.append(bit)\n",
    "            num= num // 10\n",
    "        res = 0\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            res = res * 10 + nums[i]\n",
    "        return res\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "        for i in range(1, n+1):\n",
    "            if self.change(i) == 0 or self.change(i) == i:\n",
    "                continue\n",
    "            cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        check = [0,0,1,-1,-1,1,1,-1,0,1]\n",
    "        ans=0\n",
    "        for i in range(1,n+1):\n",
    "            num = [int(digit) for digit in str(i)]\n",
    "            valid,diff = True, False\n",
    "            for digit in num:\n",
    "                if check[digit]==-1:\n",
    "                    valid=False\n",
    "                elif check[digit]==1:\n",
    "                    diff=1\n",
    "            if valid and diff:\n",
    "                ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            ok, x = False, i\n",
    "            while x != 0:\n",
    "                t = x % 10\n",
    "                x = x // 10\n",
    "                if t == 2 or t == 5 or t == 6 or t == 9:\n",
    "                    ok = True\n",
    "                elif t != 0 and t != 1 and t != 8:\n",
    "                    ok = False\n",
    "                    break\n",
    "            ans = ans + 1 if ok else ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def rotatedDigits(self, n: int) -> int:\r\n",
    "        #判断是否为好数\r\n",
    "        # 可以出现2 <-> 5, 6 <-> 9 , 0,1,8\r\n",
    "        # 不能出现3,4,7\r\n",
    "        bad = [3,4,7]\r\n",
    "        good = [2,5,6,9]\r\n",
    "        def isGood(num):\r\n",
    "            flag = False\r\n",
    "            while num:\r\n",
    "                # 按位判断\r\n",
    "                num, r = divmod(num, 10)\r\n",
    "                if r in bad:\r\n",
    "                    return False\r\n",
    "                if r in good:\r\n",
    "                    flag = True\r\n",
    "            return flag\r\n",
    "        ans = 0\r\n",
    "        for i in range(1, n + 1):\r\n",
    "            if isGood(i):\r\n",
    "                ans += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        d = dict(zip(\"0125689\", \"0152986\"))\n",
    "        def check(x):\n",
    "            s1, s2 = str(x), \"\"\n",
    "            for c in s1:\n",
    "                if c in \"347\": return False\n",
    "                s2 += d[c]\n",
    "            return s1 != s2\n",
    "        return sum(check(x) for x in range(1, n + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        \n",
    "        def isGood(x):\n",
    "            y = {\"2\", \"5\", \"6\", \"9\"}\n",
    "            n = {\"3\", \"4\", \"7\"}\n",
    "            flag = False\n",
    "            for i in str(x):\n",
    "                if i in n:\n",
    "                    return False\n",
    "                if i in y:\n",
    "                    flag = True\n",
    "            return flag\n",
    "        \n",
    "        ret = 0\n",
    "        for i in range(1, n+1):\n",
    "            if isGood(i):\n",
    "                ret += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        check = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1]\n",
    "        digits = [int(digit) for digit in str(n)]\n",
    "\n",
    "        @cache\n",
    "        def dfs(pos: int, bound: bool, diff: bool) -> int:\n",
    "            if pos == len(digits):\n",
    "                return int(diff)\n",
    "            ret = 0\n",
    "            for i in range(0, (digits[pos] if bound else 9) + 1):\n",
    "                if check[i] != -1:\n",
    "                    ret += dfs(\n",
    "                        pos + 1, bound and i == digits[pos], diff or check[i] == 1\n",
    "                    )\n",
    "            return ret\n",
    "\n",
    "        ans = dfs(0, True, False)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def rotatedDigits(self, n: int) -> int:\r\n",
    "        #判断是否为好数\r\n",
    "        # 可以出现2 <-> 5, 6 <-> 9 , 0,1,8\r\n",
    "        bad = [3,4,7]\r\n",
    "        good = [2,5,6,9]\r\n",
    "        def isGood(num):\r\n",
    "            flag = False\r\n",
    "            while num:\r\n",
    "                # 按位判断\r\n",
    "                num, r = divmod(num, 10)\r\n",
    "                if r in bad:\r\n",
    "                    return False\r\n",
    "                if r in good:\r\n",
    "                    flag = True\r\n",
    "            return flag\r\n",
    "        ans = 0\r\n",
    "        for i in range(1, n + 1):\r\n",
    "            if isGood(i):\r\n",
    "                ans += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "rotats=[0,1,2,5,6,8,9]\r\n",
    "def isRotated(num):\r\n",
    "    res=0\r\n",
    "    while num:\r\n",
    "        if num%10 not in rotats:\r\n",
    "            return False\r\n",
    "        if num%10 in [2,5,6,9]:\r\n",
    "            res+=1\r\n",
    "        num=num//10\r\n",
    "    return res>0\r\n",
    "class Solution:\r\n",
    "    def rotatedDigits(self, n: int) -> int:\r\n",
    "        res=0\r\n",
    "        for i in range(1,n+1):\r\n",
    "            res+=isRotated(i)\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        s=0\n",
    "        a={'0','1','2','5','6','8','9'}\n",
    "        b={'0','1','8'}\n",
    "        for i in range(1,n+1):\n",
    "            N=set(str(i))\n",
    "            if N.issubset(a) and not N.issubset(b): \n",
    "                s=s+1\n",
    "        return s \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIFFS = (0, 0, 1, -1, -1, 1, 1, -1, 0, 1)\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i: int, have: bool, is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return int(have)\n",
    "\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):\n",
    "                if DIFFS[d] != -1:\n",
    "                    res += f(i + 1, have or DIFFS[d], is_limit and d == up)\n",
    "            return res\n",
    "        return f(0, False, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        d = dict(zip(\"0125689\", \"0152986\"))\n",
    "        def check(x):\n",
    "            s1, s2 = str(x), \"\"\n",
    "            for c in s1:\n",
    "                if c in \"347\": return False\n",
    "                s2 += d[c]\n",
    "            return s1 != s2\n",
    "        return sum(check(x) for x in range(1, n + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        # ans = 0\n",
    "        # for x in range(1,n + 1):\n",
    "        #     cnt = Counter(str(x))\n",
    "        #     if cnt['3'] + cnt['4'] + cnt['7'] > 0:\n",
    "        #         continue\n",
    "        #     if cnt['2'] + cnt['5'] + cnt['6'] + cnt['9'] > 0:\n",
    "        #         ans += 1\n",
    "        # return ans\n",
    "        nums = [0,0,1,-1,-1,1,1,-1,0,1]\n",
    "        n = str(n)\n",
    "        N = len(n)\n",
    "        @cache\n",
    "        def dfs(i,is_limit,is_valid):\n",
    "            if i == N:\n",
    "                return int(is_valid)\n",
    "            up = int(n[i]) if is_limit else 9\n",
    "            ans = 0\n",
    "            for j in range(up + 1):\n",
    "                if nums[j] != -1:\n",
    "                    ans += dfs(i + 1,is_limit and j == up,is_valid or (nums[j] == 1))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        check=[0,0,1,-1,-1,1,1,-1,0,1]\n",
    "        ans=0\n",
    "        for i in range(1,n+1):\n",
    "            num=[int(digit) for digit in str(i)]\n",
    "            valid,diff=True,False\n",
    "            for digit in num:\n",
    "                if check[digit]==-1:\n",
    "                    valid=False\n",
    "                    break\n",
    "                elif check[digit]==1:\n",
    "                    diff=True\n",
    "            if valid and diff:\n",
    "                ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        num = 0\n",
    "        for a in range(0, n+1):\n",
    "            sa = str(a)\n",
    "            if (\"3\" in sa) or (\"4\" in sa) or (\"7\" in sa):\n",
    "                continue\n",
    "            if not( (\"2\" in sa) or (\"5\" in sa) or (\"6\" in sa) or (\"9\" in sa) ):\n",
    "                continue\n",
    "            num += 1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        dp_list = [1] * (n + 1)\n",
    "        answer = 0\n",
    "        invalid_set = {3, 4, 7}\n",
    "        depending_set = {0, 1, 8}\n",
    "        valid_set = {2, 5, 6, 9}\n",
    "        for integer in range(1, n + 1):\n",
    "            single_digit = integer % 10\n",
    "            prior_dp = integer // 10 \n",
    "            if single_digit in invalid_set:\n",
    "                dp_list[integer] = 0\n",
    "            elif single_digit in depending_set:\n",
    "                dp_list[integer] = dp_list[prior_dp]\n",
    "                if dp_list[integer] == 2:\n",
    "                    answer += 1 \n",
    "            else:\n",
    "                if dp_list[prior_dp]:\n",
    "                    dp_list[integer] = 2\n",
    "                    answer += 1 \n",
    "                else:\n",
    "                    dp_list[integer] = 0\n",
    "        return answer\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        def isGood(x):\n",
    "            set1=set('018')\n",
    "            set2=set('2569')\n",
    "            set3=set('347')\n",
    "            flag=False\n",
    "            for c in str(x):\n",
    "                if c in set3:\n",
    "                    return False\n",
    "                if c in set2:\n",
    "                    flag=True\n",
    "            return flag\n",
    "        count=0\n",
    "        for i in range(1,n+1):\n",
    "            if isGood(i):\n",
    "                count+=1\n",
    "        return count\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            ok, x = False, i\n",
    "            while x != 0:\n",
    "                t = x % 10\n",
    "                x = x // 10\n",
    "                if t == 2 or t == 5 or t == 6 or t == 9:\n",
    "                    ok = True\n",
    "                elif t != 0 and t != 1 and t != 8:\n",
    "                    ok = False\n",
    "                    break\n",
    "            ans = ans + 1 if ok else ans \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        check = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1]\n",
    "        ans=0\n",
    "        for i in range(1, n + 1):\n",
    "            num = [int(digit) for digit in str(i)]\n",
    "            valid, diff = True, False\n",
    "            for digit in num:\n",
    "                if check[digit] == -1:\n",
    "                    valid = False\n",
    "                elif check[digit] == 1:\n",
    "                    diff = True\n",
    "\n",
    "            if valid and diff:\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        # 3 4 7\n",
    "        cnt = 0\n",
    "        for i in range(1, n+1):\n",
    "            if self.isX(i):\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n",
    "\n",
    "\n",
    "    def isX(self, n) -> bool:\n",
    "        m = n\n",
    "        s = 0\n",
    "        d = 0\n",
    "        while n>0:\n",
    "            a = n%10\n",
    "            # print(a)\n",
    "            if a == 3 or a==4 or a==7:\n",
    "                return False\n",
    "            if a == 2:\n",
    "                a = 5\n",
    "            elif a == 5:\n",
    "                a = 2\n",
    "            elif a ==6:\n",
    "                a=9\n",
    "            elif a==9:\n",
    "                a=6\n",
    "            s = a*10**d+s\n",
    "            d+=1\n",
    "            n = n//10\n",
    "        # print(m, s)\n",
    "        if m==s:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        d = dict(zip(\"0125689\", \"0152986\"))\n",
    "        def check(x):\n",
    "            s1, s2 = str(x), \"\"\n",
    "            for c in s1:\n",
    "                if c in \"347\": return False\n",
    "                s2 += d[c]\n",
    "            return s1 != s2\n",
    "        return sum(check(x) for x in range(1, n + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        k = 0\n",
    "        for i in range(1, n+1):\n",
    "            j = str(i)\n",
    "            if '3' in j or '4' in j or '7' in j:\n",
    "                continue\n",
    "            else:\n",
    "                if '2' in j or '5'in j or '6'in j or '9' in j:\n",
    "                    k += 1\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isGood(self, n):\n",
    "        good = False\n",
    "        while n:\n",
    "            if n % 10 in [2, 5, 6, 9]:\n",
    "                good = True\n",
    "            if n % 10 in [3, 4, 7]:\n",
    "                return False\n",
    "            n //= 10\n",
    "        return good\n",
    "\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if self.isGood(i):\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        #暴力枚举\n",
    "        s={\"2\",\"5\",\"6\",\"9\"}\n",
    "        ans=0\n",
    "        for i in range(1,n+1):\n",
    "            cur=str(i)\n",
    "            if \"3\" in cur or \"7\" in cur or \"4\" in cur:\n",
    "                continue\n",
    "            for j in cur:\n",
    "                if j in s:\n",
    "                    ans+=1\n",
    "                    break\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        self.n=n\n",
    "        self.res=0\n",
    "        t=n\n",
    "        left=0\n",
    "        while t>0:\n",
    "            left+=1\n",
    "            t=t//10\n",
    "        self.help(0,left,False)\n",
    "        return self.res\n",
    "\n",
    "    def help(self, cur, left, flag):\n",
    "        if left==-1:\n",
    "            if flag:\n",
    "                self.res+=1\n",
    "            return flag\n",
    "        for i in [0,1,8]:\n",
    "            if cur+i*10**left>self.n:\n",
    "                break\n",
    "            self.help(cur+i*10**left,left-1,flag)\n",
    "        for i in [2,5,6,9]:\n",
    "            if cur+i*10**left>self.n:\n",
    "                break\n",
    "            self.help(cur+i*10**left,left-1,True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            ok, x = False, i\n",
    "            while x != 0:\n",
    "                t = x % 10\n",
    "                x = x // 10\n",
    "                if t == 2 or t == 5 or t == 6 or t == 9:\n",
    "                    ok = True\n",
    "                elif t != 0 and t != 1 and t != 8:\n",
    "                    ok = False\n",
    "                    break\n",
    "            ans = ans + 1 if ok else ans\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        cg = set([2,5,6,9])\n",
    "        ncg = set([0,1,8])\n",
    "        @cache\n",
    "        def f(indx, limit, yes):\n",
    "            if indx == -1:\n",
    "                return int(yes)\n",
    "            res, k = 0, n//(10**indx)%10 #第indx位的数字\n",
    "            for i in range(k+1 if limit else 10):\n",
    "                if i in cg or i in ncg:\n",
    "                    res += f(indx - 1, limit and i == k, yes or i in cg)\n",
    "            return res\n",
    "        return f(len(str(n))-1, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        self.mapping = {\n",
    "            0 : 0,\n",
    "            1 : 1,\n",
    "            2 : 5,\n",
    "            5 : 2,\n",
    "            6 : 9,\n",
    "            8 : 8,\n",
    "            9 : 6\n",
    "        }\n",
    "        def isValid(n):\n",
    "            num = n\n",
    "            rotated = 0\n",
    "            stack = []\n",
    "            while num > 0:\n",
    "                if num % 10 not in self.mapping:\n",
    "                    return False\n",
    "                stack.append(self.mapping[num % 10])\n",
    "                num //= 10\n",
    "            while stack:\n",
    "                rotated = rotated * 10 + stack.pop()\n",
    "            return rotated != n\n",
    "        \n",
    "        result = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if isValid(i):\n",
    "                result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        dic = {\"0\": \"0\", '1': '1', '2': '5', '5': '2', '6': '9', '8': '8', '9': '6'}\n",
    "        return sum(not (any(c not in dic for c in str(i)) or all(c == dic[c] for c in str(i))) for i in range(1, n + 1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "\n",
    "        check = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1]\n",
    "        ans = 0\n",
    "        nums = n\n",
    "        for i in range(1, nums + 1):\n",
    "            \n",
    "            num = [int(digit) for digit in str(i)]\n",
    "            valid, diff = True, False\n",
    "            for ch in num:\n",
    "                if check[int(ch)] == -1:\n",
    "                    valid = False\n",
    "                    break\n",
    "                elif check[int(ch)] == 0:\n",
    "                    continue\n",
    "                else:\n",
    "                    diff = True\n",
    "            if valid and diff:\n",
    "                ans += 1\n",
    "        \n",
    "        return  ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        #暴力枚举\n",
    "        s={\"2\",\"5\",\"6\",\"9\"}\n",
    "        ans=0\n",
    "        for i in range(1,n+1):\n",
    "            cur=str(i)\n",
    "            if \"3\" in cur or \"7\" in cur or \"4\" in cur:\n",
    "                continue\n",
    "            for j in cur:\n",
    "                if j in s:\n",
    "                    ans+=1\n",
    "                    break\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        dp_list = [1] * (n + 1)\n",
    "        answer = 0\n",
    "        invalid_set = {3, 4, 7}\n",
    "        depending_set = {0, 1, 8}\n",
    "        valid_set = {2, 5, 6, 9}\n",
    "        for integer in range(1, n + 1):\n",
    "            single_digit = integer % 10\n",
    "            prior_dp = integer // 10 \n",
    "            if single_digit in invalid_set:\n",
    "                dp_list[integer] = 0\n",
    "            elif single_digit in depending_set:\n",
    "                dp_list[integer] = dp_list[prior_dp]\n",
    "                if dp_list[integer] == 2:\n",
    "                    answer += 1 \n",
    "            else:\n",
    "                if dp_list[prior_dp]:\n",
    "                    dp_list[integer] = 2\n",
    "                    answer += 1 \n",
    "                else:\n",
    "                    dp_list[integer] = 0\n",
    "        return answer\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        d = dict(zip(\"0125689\", \"0152986\"))\n",
    "        def check(x):\n",
    "            s1, s2 = str(x), \"\"\n",
    "            for c in s1:\n",
    "                if c in \"347\": return False\n",
    "                s2 += d[c]\n",
    "            return s1 != s2\n",
    "        return sum(check(x) for x in range(1, n + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        # 奇怪的题目\n",
    "        check = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1]\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1): \n",
    "            num = [int(digit) for digit in str(i)]\n",
    "            valid1, valid2 = True, False\n",
    "            for digit in num: \n",
    "                if check[digit] == -1: \n",
    "                    valid1 = False\n",
    "                elif check[digit] == 1: \n",
    "                    valid2 = True\n",
    "            if valid1 and valid2: \n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        # 奇怪的题目\n",
    "        check = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1] # 2 5 6 9必须有，0 1 8可有可无， 3 4 7不能有！\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1): \n",
    "            num = [int(digit) for digit in str(i)]\n",
    "            valid1, valid2 = True, False\n",
    "            for digit in num: \n",
    "                if check[digit] == -1: \n",
    "                    valid1 = False\n",
    "                elif check[digit] == 1: \n",
    "                    valid2 = True\n",
    "            if valid1 and valid2: \n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        dp = [0,0,1,-1,-1,1,1,-1,0,1] + [0]*(n-9)\n",
    "        for i in range(n+1):\n",
    "            if dp[i//10]==-1 or dp[i%10]==-1:\n",
    "                dp[i]=-1\n",
    "            elif dp[i//10]==1 or dp[i%10]==1:\n",
    "                dp[i]=1\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        DIFF = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1]\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i, curr, is_limit):\n",
    "            if i == len(s): return curr > 0\n",
    "            ans = 0\n",
    "            upper = int(s[i]) if is_limit else 9\n",
    "            for d in range(upper + 1):\n",
    "                if DIFF[d] != -1:\n",
    "                    ans += dfs(i + 1, curr + DIFF[d], is_limit and d == upper)\n",
    "            return ans\n",
    "        return dfs(0, 0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        dic1 = {'2','5','6','9'}\n",
    "        dic2 = {'0','1','8'}\n",
    "        def check(n: int) -> bool:\n",
    "            s = str(n)\n",
    "            f = False\n",
    "            for i in s:\n",
    "                if i in dic1:\n",
    "                    f = True\n",
    "                elif i in dic2:\n",
    "                    continue\n",
    "                else :\n",
    "                    return False\n",
    "            return f\n",
    "        res = 0\n",
    "        for i in range(1,n+1):\n",
    "            if check(i):\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        cnt=0\n",
    "        arr=[1,1,0,-1,-1,0,0,-1,1,0]\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            num=str(i)\n",
    "            f1=0\n",
    "            f2=0\n",
    "            f3=0\n",
    "            for x in num:\n",
    "                x=int(x)\n",
    "                if arr[x]==1:\n",
    "                    f1=1\n",
    "                elif arr[x]==0:\n",
    "                    f2=1\n",
    "                elif arr[x]==-1:\n",
    "                    f3=1\n",
    "            #print(i,f1,f2)\n",
    "            if f2==1 and f3==0:\n",
    "                cnt+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        check = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            num = [int(digit) for digit in str(i)]\n",
    "            valid, diff = True, False\n",
    "            for digit in num:\n",
    "                if check[digit] == -1:\n",
    "                    valid = False\n",
    "                elif check[digit] == 1:\n",
    "                    diff = True\n",
    "            if valid and diff:\n",
    "                ans += 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "       s = str(n)\n",
    "       l = len(s)\n",
    "       legal = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1]\n",
    "\n",
    "       @cache\n",
    "       def dfs(i: int, hasDiff: bool, isLimit: bool, isNum: bool) -> int:\n",
    "          if i == l:\n",
    "             return hasDiff\n",
    "          res = 0\n",
    "          if not isNum:\n",
    "             res += dfs(i + 1, False, False, False)\n",
    "          up = int(s[i]) if isLimit else 9\n",
    "          for d in range(0 if isNum else 1, up + 1):\n",
    "             if legal[d] != -1:\n",
    "                res += dfs(i + 1, hasDiff or legal[d], isLimit and d == up, True)\n",
    "          return res\n",
    "       return dfs(0, False, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        set1=set('018')\n",
    "        set2=set('2569')\n",
    "        set3=set('347')\n",
    "        def helper(x):\n",
    "            flag=False\n",
    "            for c in str(x):\n",
    "                if c in set3:\n",
    "                    return False\n",
    "\n",
    "                if c in set2:\n",
    "                    flag=True\n",
    "            return flag\n",
    "        count=0\n",
    "        for i in range(1,n+1):\n",
    "            if helper(i):\n",
    "                count+=1\n",
    "        return count\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        s=str(n)\n",
    "        @cache\n",
    "        def dfs(i,is_limit,is_num,flag):  \n",
    "            if i==len(s):\n",
    "                return int(flag)\n",
    "            res=0\n",
    "            if not is_num:\n",
    "                res=dfs(i+1,False,False,False) \n",
    "            l=0 if is_num else 1\n",
    "            r=int(s[i]) if is_limit else 9\n",
    "            for d in range(l,r+1):\n",
    "                if d in [0,1,8]:\n",
    "                    res+=dfs(i+1,is_limit and d==r,True,flag)\n",
    "                elif d in [2,5,6,9]:\n",
    "                    res+=dfs(i+1,is_limit and d==r,True,True)\n",
    "            return res\n",
    "        return dfs(0,True,False,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        d = dict(zip(\"0125689\", \"0152986\"))\n",
    "        def check(x):\n",
    "            s1, s2 = str(x), \"\"\n",
    "            for c in s1:\n",
    "                if c in \"347\": return False\n",
    "                s2 += d[c]\n",
    "            return s1 != s2\n",
    "        return sum(check(x) for x in range(1, n + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        check = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1]\n",
    "        digits = [int(digit) for digit in str(n)]\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(i, is_limit, is_num, valid):\n",
    "            if i == len(digits):\n",
    "                return valid\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += dfs(i + 1, False, False, False)\n",
    "            d0 = 0 if is_num else 1\n",
    "            up = digits[i] if is_limit else 9\n",
    "            for d in range(d0, up + 1):\n",
    "                if check[d] == -1:\n",
    "                    continue\n",
    "                res += dfs(i + 1, is_limit and d == digits[i], True, valid or check[d] == 1)\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0, True, False, False)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        n_list = list(str(n))\n",
    "        length = len(str(n))\n",
    "        dd = [0,0,1,-1,-1,1,1,-1,0,1]\n",
    "        def f(index, is_num, is_limit):\n",
    "\n",
    "\n",
    "            if index==length:\n",
    "                return 1 if is_num else 0\n",
    "            res = 0\n",
    "\n",
    "            up = int(n_list[index]) if is_limit else 9\n",
    "\n",
    "            for i in range(up+1):\n",
    "                if dd[i]!=-1:\n",
    "                    res+=f(index+1, is_num or dd[i]==1, is_limit and i==up)\n",
    "            return res\n",
    "        \n",
    "        return f(0, False, True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        digits, goods = \"0125689\", \"2569\"\n",
    "        @cache\n",
    "        def f(i, isGood, isLimit, isNum):\n",
    "            if i == len(s): \n",
    "                return int(isNum and isGood)\n",
    "            res = 0 if isNum else f(i + 1, False, False, False)\n",
    "\n",
    "            up = int(s[i]) if isLimit else 9\n",
    "            down = 1-int(isNum)\n",
    "            for d in \"0125689\":\n",
    "                if down <= int(d) <= up:\n",
    "                    res += f(i+1, isGood or d in goods, isLimit and int(d) == up, True)\n",
    "            return res\n",
    "        return f(0, False, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "\n",
    "        # 0 1 8\n",
    "        # 2 5\n",
    "        # 6 9\n",
    "        @cache\n",
    "        def f(i: int, have: bool, limit: bool, isNum: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return int(have and isNum)\n",
    "            ans = 0\n",
    "            if not isNum:\n",
    "                ans = f(i + 1, have, False, False)\n",
    "            up = int(s[i]) if limit else 9\n",
    "            for d in range(1 - int(isNum), up+1):\n",
    "                if d in [2, 5, 6, 9]:\n",
    "                    ans += f(i + 1, True, limit and up == d, True)\n",
    "                elif d in [0, 1, 8]:\n",
    "                    ans += f(i + 1, True if have else False, limit and up == d, True)\n",
    "            return ans\n",
    "        return f(0, False, True, False)\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        t = set([3,4,7])\n",
    "        same = set([0,1,8])\n",
    "        @cache\n",
    "        def f(i:int,is_limit:int,not_same:bool)->int:\n",
    "            if i == len(s):\n",
    "                return int(not_same)\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for j in range(up+1):\n",
    "                if j in t:\n",
    "                    continue\n",
    "                res += f(i+1,is_limit and j == up, not_same or j not in same)\n",
    "            return res\n",
    "        return f(0,True,False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIFF = [0,0,1,-1,-1,1,1,-1,0,1]\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        # 动态规划\n",
    "        # 1、确定dp数组的下标及含义\n",
    "        # dp[i]表示从1到i中好数的个数\n",
    "        # 2、确定递推公式\n",
    "        # \n",
    "        # 3、初始化dp数组\n",
    "\n",
    "        # 4、确定遍历顺序\n",
    "        \n",
    "        s = str(n)\n",
    "\n",
    "        def f(i: int, has_diff: bool, is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return has_diff  # 只有包含2/5/6/9才算一个好数\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(0, up+1):  # 枚举要填入的数字 d\n",
    "                if DIFF[d] != -1:\n",
    "                    res += f(i+1, has_diff or DIFF[d], is_limit and d == up)\n",
    "            return res\n",
    "        return f(0, False, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        other = {2, 5, 6, 9}\n",
    "        rotate = {0, 1, 8}\n",
    "        @cache\n",
    "        def dfs(s:str, flag:bool):\n",
    "            if not s:\n",
    "                return [0, 1]\n",
    "            up = int(s[0]) if flag else 9\n",
    "            res = [0, 0]\n",
    "            for i in range(up + 1):\n",
    "                tmp = dfs(s[1:], flag & (i == up))\n",
    "                if i in other:               \n",
    "                    res[0] += tmp[0] + tmp[1]\n",
    "                elif i in rotate:\n",
    "                    res[0] += tmp[0]\n",
    "                    res[1] += tmp[1]\n",
    "            return res\n",
    "        ans = dfs(str(n), True)\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\r\n",
    "class Solution:\r\n",
    "    def rotatedDigits(self, n: int) -> int:\r\n",
    "        flags=[0,0,1,-1,-1,1,1,-1,0,1]\r\n",
    "        \r\n",
    "        digits=[int(d) for d in str(n)]\r\n",
    "\r\n",
    "        @lru_cache\r\n",
    "        def counter(pos,bound,diff):\r\n",
    "            if pos==len(digits):\r\n",
    "                return int(diff)\r\n",
    "            \r\n",
    "            ret=0\r\n",
    "            for i in range(0,(9 if not bound else digits[pos])+1):\r\n",
    "                if flags[i]==-1:\r\n",
    "                    continue\r\n",
    "                ret+=counter(\r\n",
    "                    pos+1,\r\n",
    "                    bound and i==digits[pos],\r\n",
    "                    diff or flags[i]==1\r\n",
    "                )\r\n",
    "            return ret\r\n",
    "        \r\n",
    "        return counter(0,True,False)\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        diff = [2, 5, 6, 9]\n",
    "        same = [0, 1, 8]\n",
    "        @cache\n",
    "        def dfs(i, cnt, is_limit, is_num):\n",
    "            if i == len(s): \n",
    "                if cnt > 0:\n",
    "                    return int(is_num)\n",
    "                else:\n",
    "                    return 0\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = dfs(i + 1, cnt, False, False)\n",
    "            low = 0 if is_num else 1\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(low, up + 1):\n",
    "                if d in diff:\n",
    "                    res += dfs(i + 1, cnt + 1, is_limit and d == up, True)\n",
    "                elif d in same:\n",
    "                    res += dfs(i + 1, cnt, is_limit and d == up, True)\n",
    "            return res\n",
    "        return dfs(0, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "rotats=[0,1,2,5,6,8,9]\r\n",
    "def isRotated(num):\r\n",
    "    res=0\r\n",
    "    while num:\r\n",
    "        if num%10 not in rotats:\r\n",
    "            return False\r\n",
    "        if num%10 in [2,5,6,9]:\r\n",
    "            res+=1\r\n",
    "        num=num//10\r\n",
    "    return res>0\r\n",
    "class Solution:\r\n",
    "    def rotatedDigits(self, n: int) -> int:\r\n",
    "        res=0\r\n",
    "        for i in range(1,n+1):\r\n",
    "            res+=isRotated(i)\r\n",
    "            print(i,res)\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    f=[0]*10001\n",
    "    def doit(self,w):\n",
    "        if(self.f[w]):return\n",
    "        for i in range(1,w+1):\n",
    "            j,q=str(i),0\n",
    "            for k in j:\n",
    "                if(k=='0' or k=='1' or k=='8'):q=q*10+ord(k)-48\n",
    "                if(k=='2'):q=q*10+ord(k)-45\n",
    "                if(k=='5'):q=q*10+ord(k)-51\n",
    "                if(k=='6'):q=q*10+ord(k)-45\n",
    "                if(k=='9'):q=q*10+ord(k)-51\n",
    "                if(k=='3' or k=='4' or k=='7'):self.f[i]-=1;break\n",
    "            self.f[i]+=self.f[i-1]+(q!=i)\n",
    "    def rotatedDigits(self, n: int) -> int:\n",
    "        self.doit(10000)\n",
    "        return self.f[n]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
